package com.s6.sort3;

import java.util.Arrays;

/**
 * 计数排序
 */
public class CountingSort {

	public static void main(String[] args) {
		int[] array = {3, -3, -1, 2, 5, 3, 9, -5, 11, 10, 7};
		System.out.println("before array = " + Arrays.toString(array));
		sortInteger(array);
		System.out.println("after array = " + Arrays.toString(array));
	}

	// arr 是 int 数组
	public static void sortInteger(int[] arr) {
		if (arr.length <= 1) {
			return;
		}

		// 找出最小值 和 最大值, 确定数据的范围
		int min = arr[0];
		int max = min;
		int i, j, k;
		for (i = 1; i < arr.length; i++) {
			if (arr[i] < min) {
				min = arr[i];
			}
			if (arr[i] > max) {
				max = arr[i];
			}
		}

		// 定义计数数组  c 数组，数组长度为 max - min + 1, 区间范围为[min, max]
		int length = max - min + 1;
		int[] c = new int[length];

		// 填充 c 数组
		for (i = 0; i < arr.length; i++) {
			// 元素放置到对应下标的桶 
			c[value2Index(arr[i], min)]++;
		}

		// c 会累加各项目的值
		for (i = 1; i < c.length; i++) {
			c[i] += c[i - 1];
		}

		// 创建临时数组newArr，存储排序之后的结果 
		int[] newArr = new int[arr.length];
		for (i = arr.length - 1; i >= 0; i--) {
			// 根据数值找到对应的 c 下标对应的位置
			j = arr[i];
			k = value2Index(j, min);
			// 取出下标
			c[k]--;
			// 赋值到 newArr
			newArr[c[k]] = j;
		}

		// newArr 取代 arr
		for (i = arr.length - 1; i >= 0; i--) {
			arr[i] = newArr[i];
		}
	}
	
    // 元素放置在所在下标的桶里
    private static int value2Index(int value, int min) {
    	return value - min;
    }
}
